338. 比特位计数

暴力解法

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  const dp = [0, 1]
  const result = []
  for (let i = 0; i <= n; i++) {
    result.push(
      i
        .toString(2)
        .split('')
        .filter((item) => item === '1').length
    )
  }
  return result
}

动态规划思路

• 二进制，一个数的二倍只是左移一位，１的数量不变
• 一个奇数的　 n 二进制中包含的１的数量，就比ｎ－１多一个，
• 一个偶数　ｎ　二进制中包含的１的数量，和ｎ／２一样多．

代码实现

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function (n) {
  let dp = []
  dp[0] = 0
  for (let i = 1; i <= n; i++) {
    // dp[i] = dp[i >> 1] + (i & 1)
    if (i % 2 == 1) {
      dp[i] = dp[i - 1] + 1
    } else {
      dp[i] = dp[i / 2]
    }
  }
  return dp
}